Abstract: In this paper we propose a new methodology for determining
approximate Nash equilibria of non-cooperative bimatrixgames and,
based on that, we provide an efficient algorithm that computes 0.3393-
approximate equilibria, the best approximation till now. The methodology
is based on the formulation of an appropriate function of pairs of
mixed strategies reflecting the maximum deviation of the players˘ payoffs
from the best payoff each player could achieve given the strategy
chosen by the other. We then seek to minimize such a function using
descent procedures. As it is unlikely to be able to find global minima
in polynomial time, given the recently proven intractability of the problem,
we concentrate on the computation of stationary points and prove
that they can be approximated arbitrarily close in polynomial time and
that they have the above mentioned approximation property. Our result
provides the best till now for polynomially computable -approximate
Nash equilibria of bimatrixgames. Furthermore, our methodology for
computing approximate Nash equilibria has not been used by others.
Abstract: We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrixgames, where each player's payoffs are bounded and independent random variables, not necessarily identically distributed, but with common expectations. We show that the completely mixed uniform strategy profile, i.e. the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is an almost Nash equilibrium for random bimatrixgames, in the sense that it is, with high probability, an {\aa}-well-supported Nash equilibrium where {\aa} tends to zero as n tends to infinity.
Abstract: In this work we study the tractability of well supported approximate
Nash Equilibria (SuppNE in short) in bimatrixgames. In view
of the apparent intractability of constructing Nash Equilibria (NE in
short) in polynomial time, even for bimatrixgames, understanding the
limitations of the approximability of the problem is of great importance.
We initially prove that SuppNE are immune to the addition of arbitrary
real vectors to the rows (columns) of the row (column) player˘s
payoff matrix. Consequently we propose a polynomial time algorithm
(based on linear programming) that constructs a 0.5−SuppNE for arbitrary
win lose games.
We then parameterize our technique for win lose games, in order to
apply it to arbitrary (normalized) bimatrixgames. Indeed, this new technique
leads to a weaker {\"o}−SuppNE for win lose games, where {\"o} = √5−1
2
is the golden ratio. Nevertheless, this parameterized technique extends
nicely to a technique for arbitrary [0, 1]−bimatrixgames, which assures
a 0.658−SuppNE in polynomial time.
To our knowledge, these are the first polynomial time algorithms providing
{\aa}−SuppNE of normalized or win lose bimatrixgames, for some
nontrivial constant {\aa} ∈ [0, 1), bounded away from 1.
Abstract: We study the fundamental problem of computing an arbitrary Nash equilibrium in bimatrixgames.
We start by proposing a novel characterization of the set of Nash equilibria, via a bijective map to the solution set of a (parameterized) quadratic program, whose feasible space is the (highly structured) set of correlated equilibria.
We then proceed by proposing new subclasses of bimatrixgames for which either an exact polynomial-time construction, or at least a FPTAS, is possible. In particular, we introduce the notion of mutual (quasi-) concavity of a bimatrix game, which assures (quasi-) convexity of our quadratic program, for at least one value of the parameter. For mutually concave bimatrixgames, we provide a polynomial-time computation of a Nash equilibrium, based on the polynomial tractability of convex quadratic programming. For the mutually quasiconcave games, we provide (to our knowledge) the first FPTAS for the construction of a Nash equilibrium.
Of course, for these new polynomially tractable subclasses of bimatrixgames to be useful, polynomial-time certificates are also necessary that will allow us to efficiently identify them. Towards this direction, we provide various characterizations of mutual concavity, which allow us to construct such a certificate. Interestingly, these characterizations also shed light to some structural properties of the bimatrixgames satisfying mutual concavity. This subclass entirely contains the most popular subclass of polynomial-time solvable bimatrixgames, namely, all the constant-sum games (rank-0 games). It is though incomparable to the subclass of games with fixed rank [KT07]: Even rank-1 games may not be mutually concave (eg, Prisoner's dilemma), but on the other hand, there exist mutually concave games of arbitrary (even full) rank. Finally, we prove closeness of mutual concavity under (Nash equilibrium preserving) positive affine transformations of bimatrixgames having the same scaling factor for both payoff matrices. For different scaling factors the property is not necessarily preserved.
Abstract: We study the fundamental problem 2NASH of computing a Nash equilibrium (NE) point in bimatrixgames. We start by proposing a novel characterization of the NE set, via a bijective map to the solution set of a parameterized quadratic program (NEQP), whose feasible space is the highly structured set of correlated equilibria (CE). This is, to our knowledge, the first characterization of the subset of CE points that are in “1–1” correspondence with the NE set of the game, and contributes to the quite lively discussion on the relation between the spaces of CE and NE points in a bimatrix game (e.g., [15], [26] and [33]).
We proceed with studying a property of bimatrixgames, which we call mutually concavity (MC), that assures polynomial-time tractability of 2NASH, due to the convexity of a proper parameterized quadratic program (either NEQP, or a parameterized variant of the Mangasarian & Stone formulation [23]) for a particular value of the parameter. We prove various characterizations of the MC-games, which eventually lead us to the conclusion that this class is equivalent to the class of strategically zero-sum (SZS) games of Moulin & Vial [25]. This gives an alternative explanation of the polynomial-time tractability of 2NASH for these games, not depending on the solvability of zero-sum games. Moreover, the recognition of the MC-property for an arbitrary game is much faster than the recognition SZS-property. This, along with the comparable time-complexity of linear programs and convex quadratic programs, leads us to a much faster algorithm for 2NASH in MC-games.
We conclude our discussion with a comparison of MC-games (or, SZS-games) to kk-rank games, which are known to admit for 2NASH a FPTAS when kk is fixed [18], and a polynomial-time algorithm for k=1k=1 [2]. We finally explore some closeness properties under well-known NE set preserving transformations of bimatrixgames.
Abstract: In this paper we study the support sizes of evolutionary stable strategies (ESS) in random
evolutionary games. We prove that, when the elements of the payo matrix behave either as uniform,
or normally distributed random variables, almost all ESS have support sizes o(n), where n is the
number of possible types for a player. Our arguments are based exclusively on a stability property
that the payo submatrix indicated by the support of an ESS must satisfy.
We then combine this result with a recent result of McLennan and Berg (2005), concerning the
expected number of Nash Equilibria in normal{random bimatrixgames, to show that the expected
number of ESS is signi cantly smaller than the expected number of symmetric Nash equilibria of the
underlying symmetric bimatrix game.
Abstract: We consider applications of probabilistic techniques in the
framework of algorithmic game theory. We focus on three distinct case
studies: (i) The exploitation of the probabilistic method to demonstrate
the existence of approximate Nash equilibria of logarithmic support sizes
in bimatrixgames; (ii) the analysis of the statistical conflict that mixed
strategies cause in network congestion games; (iii) the effect of coalitions
in the quality of congestion games on parallel links.
Abstract: We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrixgames, where each player's payoffs are bounded and independent random variables, not necessarily identically distributed, but with almost common expectations. We show that the completely mixed uniform strategy profile, i.e., the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is with high probability a TeX -Nash equilibrium and a TeX -well supported Nash equilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nash equilibrium for random bimatrixgames, since it is, with high probability, an ϵ-well-supported Nash equilibrium where ϵ tends to zero as n tends to infinity.
Abstract: In view of the apparent intractability of constructing Nash Equilibria (NE
in short) in polynomial time, even for bimatrixgames, understanding the limitations
of the approximability of the problem is an important challenge.
In this work we study the tractability of a notion of approximate equilibria in bimatrixgames, called well supported approximate Nash Equilibria (SuppNE in short).
Roughly speaking, while the typical notion of approximate NE demands that each
player gets a payoff at least an additive term less than the best possible payoff, in a
SuppNE each player is assumed to adopt with positive probability only approximate
pure best responses to the opponent˘s strategy.
As a first step, we demonstrate the existence of SuppNE with small supports and
at the same time good quality. This is a simple corollary of Alth{\"o}fer˘s Approximation
Lemma, and implies a subexponential time algorithm for constructing SuppNE of
arbitrary (constant) precision.
We then propose algorithms for constructing SuppNE in win lose and normalized
bimatrixgames (i.e., whose payoff matrices take values from {0, 1} and [0, 1] respectively).
Our methodology for attacking the problem is based on the solvability of zero sum bimatrixgames (via its connection to linear programming) and provides a
0.5-SuppNE for win lose games and a 0.667-SuppNE for normalized games.
To our knowledge, this paper provides the first polynomial time algorithms constructing
{\aa}-SuppNE for normalized or win lose bimatrixgames, for any nontrivial
constant 0 ≤{\aa} <1, bounded away from 1.
Abstract: We study the existence and tractability of a notion of approximate
equilibria in bimatrixgames, called well supported approximate
Nash Equilibria (SuppNE in short).We prove existence of "−SuppNE for
any constant " 2 (0, 1), with only logarithmic support sizes for both players.
Also we propose a polynomial–time construction of SuppNE, both
for win lose and for arbitrary (normalized) bimatrixgames. The quality
of these SuppNE depends on the girth of the Nash Dynamics graph in
the win lose game, or a (rounded–off) win lose image of the original normalized
game. Our constructions are very successful in sparse win lose
games (ie, having a constant number of (0, 1)−elements in the bimatrix)
with large girth in the Nash Dynamics graph. The same holds also for
normalized games whose win lose image is sparse with large girth.
Finally we prove the simplicity of constructing SuppNE both in random
normalized games and in random win lose games. In the former case we
prove that the uniform full mix is an o(1)−SuppNE, while in the case
of win lose games, we show that (with high probability) there is either a
PNE or a 0.5-SuppNE with support sizes only 2.
